package from_0_to_50;

import java.util.Arrays;

public class Q005_longestPalindromicSubstring {
    public static void main(String[] args) {
        String str = "babadpppp";
        System.out.println("str.substring(1,2) = " + str.substring(0, 9)); // [ )
        str = longestPalindrome(str);
        System.out.println(str);
    }

    public static String longestPalindrome(String s) {
        int left = 0, right = 0;
        char[] chars = s.toCharArray();

        if (s.length() == 1)
            return s;
        else {
            int k = 1;
            for (int i = 0; i < s.length(); i++) {  // 奇数长度
                while (0 <= (i-k) && (i+k) <= s.length()){
                    if(chars[i-k] == chars[i+k])
                        k++;
                    else {
                        break;
                    }
                }
                if(2 * k > right - left){
                    left = i - k;
                    right = i + k;
                }
            }
            k = 0;
            for (int i = 0; i < s.length() - 1; i++) {     // 偶数长度
                if(chars[i] == chars[i+1]){
                    if(0 <= (i-k) && (i-k) <= s.length() && chars[i-k] == chars[i+k+1]) {
                        k++;
                    }else {
                        if(2*k+2 > right - left){
                            left = i - k;
                            right = i + k;
                        }
                    }
                }
            }
        }
        return s.substring(left, right+1);
    }
}
